package codetop;

public class lc31_next_array {
    public static void main(String[] args) {
        int[] num = {1,3,2};
        nextPermutation(num);
        for (int i : num) {
            System.out.print(i + " ");
        }
    }
    public static void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        while(i >= 0 && nums[i] >= nums[i + 1]){
            i--;
        }
        int start = 0;
        int end = n - 1;
        if(i < 0){
            reverse(start, end, nums);
            return;
        }
        int j = n - 1;
        while(j > i && nums[j] <= nums[i]){
            j--;
        }
        swap(i, j, nums);
        start = i + 1;
        end = n - 1;
        reverse(start, end, nums);

    }
    public static void swap(int i, int j, int[] ints){
        int t = ints[i];
        ints[i] = ints[j];
        ints[j] = t;
    }
    public static void reverse(int start, int end, int[] ints){
        while(start < end){
            swap(start, end, ints);
            start++;
            end--;
        }
    }
}
